//
// Created by guanyicheng on 2022/5/10.
//

#include "../../common.h"

class MyQueue {

private:
    deque<int> que;

public:
    void push(int value) {
        while (!que.empty() && value > que.back()) {
            que.pop_back();
        }
        que.emplace_back(value);
    }

    void pop(int value) {
        if (!que.empty() && que.front() == value) {
            que.pop_front();
        }
    }

    int front() {
        return que.front();
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        auto myQueue = MyQueue{};
        for (int i = 0; i < k; ++i) {
            myQueue.push(nums[i]);
        }
        auto res = vector<int>{myQueue.front()};

        for (int i = k; i < nums.size(); ++i) {
            myQueue.pop(nums[i - k]);
            myQueue.push(nums[i]);
            res.emplace_back(myQueue.front());
        }
        return res;
    }
};

int main() {
    auto v1 = vector<int>{1, 3, 1, 2, 0, 5};
    cout << Solution().maxSlidingWindow(v1, 3).size() << endl;
}